package personal_exercise;

import model.TreeNode;

import java.util.*;

public class Demo9 {


    // 797. 所有可能的路径
    private List<Integer> path = new ArrayList<>();
    private boolean[] vis;
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int n = graph.length;
        vis = new boolean[n + 1];
        dfs(0, graph);
        return res;
    }
    private void dfs(int cur,  int[][] outs) {
        path.add(cur);
        if (cur == outs.length - 1) {
            res.add(new ArrayList<>(path));
            path.remove(path.size() - 1);
            return;
        }

        vis[cur] = true;
        for(int x : outs[cur]) {
            if (!vis[x]) {
                dfs(x, outs);
            }
        }
        path.remove(path.size() - 1);
        vis[cur] = false;
    }



    // 101. 孤岛的总面积
    class Main {
        private  int n, m;
        private  int[] dx = {0,0,1,-1};
        private  int[] dy = {1,-1,0,0};
        private  boolean[][] vis;
        private  int res, count;
        private  boolean flag;

        public void main (String[] args) {
            Scanner in = new Scanner(System.in);
            n = in.nextInt(); m = in.nextInt();
            int[][] nums = new int[n][m];
            vis = new boolean[n][m];
            for (int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    nums[i][j] = in.nextInt();
                }
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (nums[i][j] == 1 && !vis[i][j]) {
                        count = 0;
                        flag = false;
                        dfs(nums, i, j);
                        if (!flag) res += count;
                    }

                }
            }

            System.out.println(res);
        }
        private void dfs(int[][] nums, int i, int j) {
            count++;
            vis[i][j] = true;

            for (int k = 0; k < 4; k++) {
                int x = i + dx[k], y = j + dy[k];
                if (x < 0 || x == n || y < 0 || y == m) {
                    flag = true;
                } else {
                    if (nums[x][y] == 1 && !vis[x][y]) {
                        dfs(nums, x, y);
                    }
                }
            }
        }
    }


    // 695. 岛屿的最大面积
    class Solution {
        int[] dx = {0,0,1,-1};
        int[] dy = {1,-1,0,0};
        boolean[][] vis;
        int n, m;
        int res, tmpSum;

        public int maxAreaOfIsland(int[][] grid) {
            n = grid.length; m = grid[0].length;
            vis = new boolean[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] == 1 && !vis[i][j]) {
                        tmpSum = 0;
                        dfs(grid, i, j);
                        res = Math.max(res, tmpSum);
                    }
                }
            }
            return res;
        }
        private void dfs(int[][] nums, int i, int j) {
            vis[i][j] = true;
            tmpSum++;

            for (int k = 0; k < 4; k++) {
                int x = i + dx[k], y = j + dy[k];
                if (x >= 0 && x < n && y >= 0 && y < m && nums[x][y] == 1 && !vis[x][y]) {
                    dfs(nums, x, y);
                }
            }
        }
    }




    // 建造最大岛屿
    class Main2 {
        private  int n, m;
        private  int[] dx = {0,0,1,-1};
        private  int[] dy = {1,-1,0,0};
        private  int sum, numb;
        // 记录每块陆地所属的岛屿编号
        private int[][] nums;
        private boolean[][] vis;
        private int maxProduct;

        public void main (String[] args) {
            Scanner in = new Scanner(System.in);
            n = in.nextInt(); m = in.nextInt();
            nums = new int[n][m];
            vis = new boolean[n][m];

            int[][] grid = new int[n][m];
            for (int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    grid[i][j] = in.nextInt();
                }
            }

            // 岛屿编号 - 面积
            Map<Integer,Integer> hash = new HashMap<>();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] == 1 && !vis[i][j]) {
                        sum = 0;
                        numb++;
                        dfs(grid, i, j);
                        hash.put(numb, sum);
                        maxProduct = Math.max(maxProduct, sum);
                    }
                }
            }

            int res = maxProduct;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] == 0) {
                        int tmp = 1;
                        boolean[] flag = new boolean[numb + 1];
                        for (int k = 0; k < 4; k++) {
                            int x =  i + dx[k], y = j + dy[k];
                            if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1) {
                                int index = nums[x][y];
                                if (!flag[index]) {
                                    tmp += hash.get(index);
                                    flag[index] = true;
                                }
                            }
                        }
                        res = Math.max(res, tmp);
                    }
                }
            }
            System.out.println(res);

        }
        private void dfs(int[][] grid, int i, int j) {
            nums[i][j] = numb;
            vis[i][j] = true;
            sum++;

            for (int k = 0; k < 4; k++) {
                int x = i + dx[k], y = j + dy[k];
                if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1 && !vis[x][y]) {
                    dfs(grid, x, y);
                }
            }
        }
    }


    // 102. 沉没孤岛
    class Main3 {
        private int n, m;
        private int[] dx = {0,0,1,-1};
        private int[] dy = {1,-1,0,0};

        public void main (String[] args) {
            Scanner in = new Scanner(System.in);
            n = in.nextInt(); m = in.nextInt();
            int[][] nums = new int[n][m];
            for (int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                    nums[i][j] = in.nextInt();
                }
            }

            for (int i = 0; i < n; i++) {
                if (nums[i][0] == 1) {
                    dfs(nums, i, 0);
                }
                if (nums[i][m - 1] == 1) {
                    dfs(nums, i, m - 1);
                }
            }
            for (int i = 0; i < m; i++) {
                if (nums[0][i] == 1) {
                    dfs(nums, 0, i);
                }
                if (nums[n - 1][i] == 1) {
                    dfs(nums, n - 1, i);
                }
            }


            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (nums[i][j] == 1) nums[i][j] = 0;
                    else if (nums[i][j] == 3) nums[i][j] = 1;
                    System.out.print(nums[i][j] + " ");
                }
                System.out.println();
            }
        }
        private void dfs(int[][] nums, int i, int j) {
            nums[i][j] = 3;

            for (int k = 0; k < 4; k++) {
                int x = i + dx[k], y = j + dy[k];
                if (x >= 0 && x < n && y >= 0 && y < m && nums[x][y] == 1) {
                    dfs(nums, x, y);
                }
            }
        }

    }




    // 101. 孤岛的总面积
    public class Main4 {
        private int n, m;
        private int[] dx = {0, 0, 1, -1};
        private int[] dy = {1, -1, 0, 0};
        private boolean[][] vis;
        private int res, count;
        private boolean flag;

        public void main(String[] args) {
            Scanner in = new Scanner(System.in);
            n = in.nextInt();
            m = in.nextInt();
            int[][] nums = new int[n][m];
            vis = new boolean[n][m];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    nums[i][j] = in.nextInt();
                }
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (nums[i][j] == 1 && !vis[i][j]) {
                        count = 0;
                        flag = false;
                        dfs(nums, i, j);
                        if (!flag) res += count;
                    }

                }
            }

            System.out.println(res);
        }

        private void dfs(int[][] nums, int i, int j) {
            count++;
            vis[i][j] = true;

            for (int k = 0; k < 4; k++) {
                int x = i + dx[k], y = j + dy[k];
                if (x < 0 || x == n || y < 0 || y == m) {
                    flag = true;
                } else {
                    if (nums[x][y] == 1 && !vis[x][y]) {
                        dfs(nums, x, y);
                    }
                }
            }
        }
    }



    // 53. 寻宝（第七期模拟笔试）
    public static void main2 (String[] args) {
        Scanner in = new Scanner(System.in);
        int v = in.nextInt(), e = in.nextInt();
        // 记录顶点到顶点之间边的权值
        int[][] grid = new int[v + 1][v + 1];
        for (int[] arr : grid) {
            Arrays.fill(arr, 10001);
        }
        while (e-- > 0) {
            int v1 = in.nextInt(), v2 = in.nextInt(), val = in.nextInt();
            grid[v1][v2] = grid[v2][v1] = val;
        }

        // 记录各顶点到最小生成树的最近距离
        int[] minDist = new int[v + 1];
        Arrays.fill(minDist, 10001);
        // 记录顶点是否加入最小生成树中
        boolean[] isInTree = new boolean[v + 1];

        for (int i = 0; i < v - 1; i++) {
            // 1. 寻找未加入最小生成树且距离最近的节点
            int cur = -1, minVal = Integer.MAX_VALUE;
            for (int j = 1; j <= v; j++) {
                if (!isInTree[j] && minDist[j] < minVal) {
                    cur = j;
                    minVal = minDist[j];
                }
            }

            // 2. 将该节点加入最小生成树
            isInTree[cur] = true;

            // 3. 更新各顶点到最小生成树的距离
            for (int j = 1; j <= v; j++) {
                if (!isInTree[j] && grid[cur][j] < minDist[j]) {
                    minDist[j] = grid[cur][j];
                }
            }
        }

        int res = 0;
        for (int i = 2; i <= v; i++) {
            res += minDist[i];
        }
        System.out.println(res);
    }
    //public class Main {
    //    static int[] father;
    //    public static void main (String[] args) {
    //        Scanner in = new Scanner(System.in);
    //        int v = in.nextInt(), e = in.nextInt();
    //        // 并查集初始化
    //        father = new int[v + 1];
    //        for (int i = 1; i <= v; i++) {
    //            father[i] = i;
    //        }
    //
    //        int[][] edges = new int[e][3];
    //        for (int i = 0; i < e; i++) {
    //            int v1 = in.nextInt(), v2 = in.nextInt(), val = in.nextInt();
    //            edges[i] = new int[]{v1, v2, val};
    //        }
    //
    //        // 记录加入最小生成树的边
    //        // boolean[] vis = new boolean[e];
    //
    //        // 1. 对边的权值从小到大进行排序
    //        Arrays.sort(edges, (a, b) -> a[2] - b[2]);
    //        // 2. 对边进行遍历，依次检查边的两个节点是否在同一集合
    //        int res = 0;
    //        for (int i = 0; i < e; i++) {
    //            int x = edges[i][0], y =  edges[i][1];
    //            if (!isSame(x, y)) {
    //                join(x, y);
    //                res += edges[i][2];
    //                vis[i] = true;
    //            }
    //        }
    //        System.out.println(res);
    //
    //        // 打印最小生成树的边
    //        // for (int i = 0; i < e; i++) {
    //        //     if (vis[i]) {
    //        //       System.out.println(edges[i][0] + " -> " + edges[i][1]);
    //        //     }
    //        // }
    //    }
    //    private static int find(int x) {
    //        if (father[x] == x) return x;
    //        return father[x] = find(father[x]);
    //    }
    //    private static void join(int x, int y) {
    //        x = find(x);
    //        y = find(y);
    //        // if (x == y) return;
    //        father[x] = y;
    //    }
    //    private static boolean isSame(int x, int y) {
    //        return find(x) == find(y);
    //    }
    //}





    // 47. 参加科学大会（第六期模拟笔试）
    // dijkstra 朴素版
    public static void main3(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        int[][] outs = new int[n + 1][n + 1];
        for (int[] arr : outs) {
            Arrays.fill(arr, 0x3f3f3f3f);
        }
        while (m-- > 0) {
            int s = in.nextInt(), e = in.nextInt(), v = in.nextInt();
            outs[s][e] = v;
        }

        // 记录每个站点到源点的最小距离
        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, 0x3f3f3f3f);
        minDist[1] = 0;
        // 记录各节点是否加入最短路径中
        boolean[] vis = new boolean[n + 1];

        // 记录最短路径经过的边
//        int[] father = new int[n + 1];

        for (int i = 0; i < n; i++) {
            int cur = -1;
            int minVal = 0x3f3f3f3f;

            for (int j = 1; j <= n; j++) {
                // 1. 寻找距离源点最近且未被访问的节点
                if (!vis[j] && minDist[j] < minVal) {
                    cur = j;
                    minVal = minDist[j];
                }
            }
            if (cur == -1) break;

            // 2. 将该节点加入最短路径中
            vis[cur] = true;

            // 3. 更新其余节点到源点的最短距离
            for (int k = 1; k <= n; k++) {
                if (outs[cur][k] < 0x3f3f3f3f && !vis[k] && minVal + outs[cur][k] < minDist[k]) {
                    minDist[k] = minVal + outs[cur][k];
//                    father[k] = cur;
                }
            }
        }


        System.out.println(minDist[n] < 0x3f3f3f3f ? minDist[n] : -1);
//        for (int i = n; i >= 1; i--) {
//            for (int j = i; j != 0; j = father[j]) {
//                System.out.print(j + " -> ");
//            }
//            System.out.println();
//        }
    }

    // dijkstra 堆优化版
    //class Pair<U, V> {
    //    public final U first;
    //    public final V second;
    //
    //    public Pair(U first, V second) {
    //        this.first = first;
    //        this.second = second;
    //    }
    //}
    //
    //
    //class MyComparison implements Comparator<Pair<Integer, Integer>> {
    //    @Override
    //    public int compare(Pair<Integer, Integer> lhs, Pair<Integer, Integer> rhs) {
    //        return Integer.compare(lhs.second, rhs.second);
    //    }
    //}
    //
    //public class Main {
    //
    //    public static void main (String[] args) {
    //        Scanner in = new Scanner(System.in);
    //        int n = in.nextInt(), m = in.nextInt();
    //        List<List<int[]>> outs = new ArrayList<>();
    //        for (int i = 0; i <= n; i++) {
    //            outs.add(new ArrayList<>());
    //        }
    //        while (m-- > 0) {
    //            int s = in.nextInt(), e = in.nextInt(), v = in.nextInt();
    //                             // 边、权值
    //            outs.get(s).add(new int[]{e, v});
    //        }
    //
    //        // 记录每个站点到源点的最小距离
    //        int[] minDist = new int[n + 1];
    //        Arrays.fill(minDist, 0x3f3f3f3f);
    //        minDist[1] = 0;
    //        // 记录各节点是否加入最短路径中
    //        boolean[] vis = new boolean[n + 1];
    //        // int[]: 节点，节点到源点的最短距离
    //        PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(new MyComparison());
    //        pq.offer(new Pair(1, 0));
    //
    //        while (!pq.isEmpty()) {
    //            // 1. 获取距离源点最近且未被访问的节点
    //            Pair<Integer, Integer> top = pq.poll();
    //            int cur = top.first, minVal = top.second;
    //            // 该节点已加入最短路径
    //            if (vis[cur]) continue;
    //
    //            // 2. 将该节点加入最短路径中
    //            vis[cur] = true;
    //
    //            // 3. 遍历该节点所连接的边，更新其余节点到源点的最短距离
    //            for (int[] edge : outs.get(cur)) {
    //                int j = edge[0], val = edge[1];
    //                if (!vis[j] && minDist[cur] + val < minDist[j]) {
    //                    minDist[j] = minDist[cur] + val;
    //                    pq.offer(new Pair(j, minDist[j]));
    //                }
    //
    //            }
    //        }
    //
    //        System.out.println(minDist[n] < 0x3f3f3f3f ? minDist[n] : -1);
    //    }
    //}




    // 94. 城市间货物运输 I
    static class Edge {
        public int from;
        public int to;
        public int val;

        public Edge(int from, int to, int val) {
            this.from = from;
            this.to = to;
            this.val = val;
        }
    }
    public static void main10 (String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt(), m = in.nextInt();
        List<Edge> outs = new ArrayList<>();
        while (m-- > 0) {
            int s = in.nextInt(), t = in.nextInt(), v = in.nextInt();
            outs.add(new Edge(s, t, v));
        }

        int[] minDist = new int[n + 1];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[1] = 0;

        // 对所有边松弛 n - 1 次
        for (int i = 0; i < n - 1; i++) {
            for (Edge e : outs) {
                int from = e.from, to = e.to, val = e.val;
                // minDist[from] < Integer.MAX_VALUE 防止从未计算过的节点出发
                if (minDist[from] < Integer.MAX_VALUE && minDist[from] + val < minDist[to]) {
                    minDist[to] = minDist[from] + val;
                }
            }
        }

        if (minDist[n] == Integer.MAX_VALUE) {
            System.out.println("unconnected");
        } else {
            System.out.println(minDist[n]);
        }
    }

    // 队列优化版本
    // static class Edge {
    //        public int to;
    //        public int val;
    //
    //        public Edge(int to, int val) {
    //            this.to = to;
    //            this.val = val;
    //        }
    //    }
    //
    //
    //    public static void main (String[] args) {
    //        Scanner in = new Scanner(System.in);
    //        int n = in.nextInt(), m = in.nextInt();
    //        List<Edge>[] outs = new List[n + 1];
    //        Arrays.setAll(outs, i -> new ArrayList<>());
    //        while (m-- > 0) {
    //            int s = in.nextInt(), t = in.nextInt(), v = in.nextInt();
    //            outs[s].add(new Edge(t, v));
    //        }
    //
    //        int start = 1; // 起点
    //        int end = n;   // 终点
    //
    //        // minDist[i]: 节点 i 到源点的最短距离
    //        int[] minDist = new int[n + 1];
    //        Arrays.fill(minDist, Integer.MAX_VALUE);
    //        minDist[start] = 0;
    //
    //        // 记录节点是否已加入队列
    //        boolean[] vis = new boolean[n + 1];
    //        vis[start] = true;
    //
    //        Queue<Integer> q = new LinkedList<>();
    //        q.offer(start);
    //
    //        while (!q.isEmpty()) {
    //            int from = q.poll();
    //            vis[from] = false;
    //
    //            for (Edge e : outs[from]) {
    //                int to = e.to, val = e.val;
    //                if (minDist[to] > minDist[from] + val) {
    //                    minDist[to] = minDist[from] + val;
    //                    if (!vis[to]) {
    //                        q.offer(to);
    //                        vis[to] = true;
    //                    }
    //                }
    //            }
    //        }
    //
    //        if (minDist[end] == Integer.MAX_VALUE) {
    //            System.out.println("unconnected");
    //        } else {
    //            System.out.println(minDist[end]);
    //        }
    //    }




    // 95. 不同的二叉搜索树 II
    public List<TreeNode> generateTrees(int n) {
        return geneTrees(1, n);
    }
    // 返回 satrt ~ end 这个范围可能生成的二叉搜索树的集合
    private List<TreeNode> geneTrees(int begin, int end) {
        List<TreeNode> allTrees = new ArrayList<>();
        if (begin > end) {
            allTrees.add(null);
            return allTrees;
        }

        // 枚举以 i 为根节点的二叉搜索树
        for (int i = begin; i <= end; i++) {
            // 以 i 为根节点，所有可行的左子树的集合
            List<TreeNode> leftTrees =  geneTrees(begin, i - 1);
            // 以 i 为根节点，所有可行的右子树的集合
            List<TreeNode> rightTrees = geneTrees(i + 1, end);

            for (TreeNode left : leftTrees) {
                for (TreeNode right : rightTrees) {
                    TreeNode root = new TreeNode(i);
                    root.left = left;
                    root.right = right;
                    allTrees.add(root);
                }
            }
        }
        return allTrees;
    }




    // 769. 最多能完成排序的块
    public int maxChunksToSorted(int[] arr) {
        // 若下标为 i 的元素，没有任一下标大于 i 的元素小于等于 arr[i]，则将该元素分为一块
        int n = arr.length;
        int left = 0;
        int res = 0;
        while (left < n) {
            int right = left + 1;
            int index = left;           // 统计小于等于 arr[left] 的最右下标
            int blockMaxIndex = left;   // 统计当前块内的最大元素下标
            while (right < n) {
                if (arr[right] < arr[left]) {
                    index = right;
                    left = blockMaxIndex;
                }else if (arr[right] > arr[blockMaxIndex]){
                    blockMaxIndex = right;  // 块内最大元素可能发生改变
                }
                right++;
            }

            res++;
            left = index + 1;
        }
        return res;
    }




    // 768. 最多能完成排序的块 II
    public int maxChunksToSorted2(int[] arr) {
        // 若下标为 i 的元素，没有任一下标大于 i 的元素小于等于 arr[i]，则将该元素分为一块
        int n = arr.length;
        int left = 0;
        int res = 0;
        while (left < n) {
            int right = left + 1;
            int index = left;           // 统计小于等于 arr[left] 的最右下标
            int blockMaxIndex = left;   // 统计当前块内的最大元素下标
            while (right < n) {
                if (arr[right] < arr[left]) {
                    index = right;
                    left = blockMaxIndex;
                }else if (arr[right] > arr[blockMaxIndex]){
                    blockMaxIndex = right;  // 块内最大元素可能发生改变
                }
                right++;
            }

            res++;
            left = index + 1;
        }
        return res;
    }




    // 1497. 检查数组对是否可以被 k 整除
    public boolean canArrange(int[] arr, int k) {
        int[] modCounts = new int[k * 2];
        for (int x : arr) {
            modCounts[x % k + k]++;
        }

        if (modCounts[k] % 2 != 0) return false;
        for (int i = 1; i < k; i++) {
            // 从 (-k, 0) 这个区间，验证模为 modCounts[-i]与modCounts[k - i]之和
            // 是否和 modCounts[i]与modCounts[i - k]之和 相等
            int mod = i - k;    // mod 即为 -i
            if (modCounts[mod + k] + modCounts[2 * k + mod] != modCounts[-mod + k] + modCounts[-mod]) return false;
        }
        return true;
    }


    // 1010. 总持续时间可被 60 整除的歌曲
    public int numPairsDivisibleBy60(int[] time) {
        int[] modCounts = new int[60];
        int res = 0;
        for (int x : time) {
            if (x % 60 == 0) {
                res += modCounts[0];
            } else {
                res += modCounts[60 - x % 60];
            }
            modCounts[x % 60]++;
        }
        return res;
    }
}
